Corelab Seminar
2010-2011
Haris Angelidakis
Approximation algorithms for 2-Stage Stochastic Optimization Problems
Abstract.
In this talk, we will continue our overview of the research done in the field of
2-stage Stochastic Optimization the last decade. We will focus on the work of David B. Shmoys and Chaitanya Swamy
on 2-stage stochastic optimization problems, and more specifically on the papers “Stochastic Optimization is (almost)
as easy as deterministic optimization” (FOCS 2004) and “The Sample Average Approximation Method for 2-stage Stochastic
Optimization” (unpublished manuscript).
We will present an FPRAS for solving a wide class of 2-stage stochastic problems which can be used, in conjuction
with rounding techniques, to yield constant factor approximation algorithms for various combinatorial problems.
We will reach this result by utilizing two different methods, the ellipsoid method and the Sample Average Approximation
Method (SAA). Both methods are widely used in various problems and present much interest, the first being used mostly for
theoretical results, while the second for much more practical applications.